package levelorder;

import java.util.LinkedList;

public class PopulatingNextRightPointersII {
    /*
    * 117.填充每个节点的下一个右侧节点指针 II
    * 给定一个 二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
    * struct Node {
    *    int val;
    *    Node *left;
    *    Node *right;
    *    Node *next;
    * }
    *
    * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。
    * 如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
    * 初始状态下，所有 next 指针都被设置为 NULL。
    *
    * 树中节点的数量在 [0, 2^12 - 1] 范围内
    * -1000 <= node.val <= 1000
    *
    * 进阶：
    * 你只能使用常量级额外空间。
    * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
    * */
    public static void main(String[] args){

    }

    // 我的想法：和116一毛一样的答案就可以，但效率不算最高
    public TheNode mySolution(TheNode root){
        if(root == null)
            return root;
        LinkedList<TheNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()){
            int len = deque.size();
            TheNode cur;
            while (len > 0){
                cur = deque.pop();
                cur.next = len == 1? null : deque.peek();
                if(cur.left != null) deque.add(cur.left);
                if(cur.right != null) deque.add(cur.right);
                len--;
            }
        }
        return root;
    }

    // 用一个虚拟头来串联每层的节点就好了，省去了队列
    public TheNode solution(TheNode root){
        TheNode cur = root;
        while (cur != null){
            // 定义一个虚拟头节点，用于将一行串联，同时记录下一次cur从何处开始
            TheNode dummyHead = new TheNode();
            // 用于移动，记录当前链表尾的节点
            TheNode pre = dummyHead;
            while (cur != null){
                if(cur.left != null){
                    pre.next = cur.left;
                    pre = pre.next;
                }
                if(cur.right != null){
                    pre.next = cur.right;
                    pre = pre.next;
                }
                cur = cur.next;
            }
            // cur指向下一行行首
            cur = dummyHead.next;
        }
        return root;
    }
}
